#define _CRT_SECURE_NO_WARNINGS

//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int head, idx, e[N], ne[N];
//int m;
//
//void init()
//{
//	head = -1;
//	idx = 0;
//}
//
//void push_head(int x)
//{
//	e[idx] = x;
//	ne[idx] = head;
//	head = idx++;
//}
//
//void push(int k, int x)
//{
//	e[idx] = x;
//	ne[idx] = ne[k];
//	ne[k] = idx++;
//}
//
//void del(int k)
//{
//	ne[k] = ne[ne[k]];
//}
//
//int main()
//{
//	cin >> m;
//
//	init();
//
//	while (m--)
//	{
//		int k, x;
//		char ch;
//		cin >> ch;
//
//		if (ch == 'H')
//		{
//			cin >> x;
//			push_head(x);
//		}
//		else if (ch == 'D')
//		{
//			cin >> k;
//			if (!k) head = ne[head];
//			else del(k - 1);
//		}
//		else
//		{
//			cin >> k >> x;
//			push(k - 1, x);
//		}
//	}
//
//	for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
//	cout << endl;
//
//	return 0;
//}


//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int r[N], l[N], e[N], idx;
//int m;
//
//void init()
//{
//    r[0] = 1;
//    l[1] = 0;
//    idx = 2;
//}
//
//void pushL(int x)
//{
//    e[idx] = x;
//    r[idx] = r[0];
//    l[r[0]] = idx;
//    r[0] = idx;
//    l[idx] = 0;
//    idx++;
//}
//
//void pushR(int x)
//{
//    e[idx] = x;
//    l[idx] = l[1];
//    r[l[1]] = idx;
//    l[1] = idx;
//    r[idx] = 1;
//    idx++;
//}
//
//void del(int k)
//{
//    r[l[k]] = r[k];
//    l[r[k]] = l[k];
//}
//
//void push(int k, int x)
//{
//    e[idx] = x;
//    r[idx] = r[k];
//    l[r[k]] = idx;
//    r[k] = idx;
//    l[idx] = k;
//    idx++;
//}
//
//int main()
//{
//    cin >> m;
//
//    init();
//
//    while (m--)
//    {
//        int k, x;
//        string op;
//        cin >> op;
//
//        if (op == "L")
//        {
//            cin >> x;
//            pushL(x);
//        }
//        else if (op == "R")
//        {
//            cin >> x;
//            pushR(x);
//        }
//        else if (op == "D")
//        {
//            cin >> k;
//            del(k + 1);
//        }
//        else if (op == "IL")
//        {
//            cin >> k >> x;
//            push(l[k + 1], x);
//        }
//        else
//        {
//            cin >> k >> x;
//            push(k + 1, x);
//        }
//    }
//
//    for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
//    cout << endl;
//
//    return 0;
//}

//
//
//#include <iostream>
//
//using namespace std;
//
//const int N = 100010;
//int head, e[N], ne[N], idx;
//int m;
//
//void init()
//{
//    head = -1;
//    idx = 0;
//}
//
//void push_head(int x)
//{
//    e[idx] = x;
//    ne[idx] = head;
//    head = idx++;
//}
//
//void del(int k)
//{
//    ne[k] = ne[ne[k]];
//}
//
//void push(int k, int x)
//{
//    e[idx] = x;
//    ne[idx] = ne[k];
//    ne[k] = idx++;
//}
//
//int main()
//{
//    cin >> m;
//
//    init();
//
//    while (m--)
//    {
//        int k, x;
//        char op;
//        cin >> op;
//
//        if (op == 'H')
//        {
//            cin >> x;
//            push_head(x);
//        }
//        else if (op == 'D')
//        {
//            cin >> k;
//            if (!k) head = ne[head];
//            else del(k - 1);
//        }
//        else 
//        {
//            cin >> k >> x;
//            push(k - 1, x);
//        }
//    }
//
//    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
//    cout << endl;
//
//    return 0;
//}
//
//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int e[N], r[N], l[N], idx;
//int m;
//
//void init()
//{
//    r[0] = 1;
//    l[1] = 0;
//    idx = 2;
//}
//
//void pushL(int x)
//{
//    e[idx] = x;
//    r[idx] = r[0];
//    l[r[0]] = idx;
//    r[0] = idx;
//    l[idx] = 0;
//    idx++;
//}
//
//void pushR(int x)
//{
//    e[idx] = x;
//    l[idx] = l[1];
//    r[l[1]] = idx;
//    l[1] = idx;
//    r[idx] = 1;
//    idx++;
//}
//
//void del(int k)
//{
//    r[l[k]] = r[k];
//    l[r[k]] = l[k];
//}
//
//void push(int k, int x)
//{
//    e[idx] = x;
//    r[idx] = r[k];
//    l[r[k]] = idx;
//    r[k] = idx;
//    l[idx] = k;
//    idx++;
//}
//
//int main()
//{
//    cin.tie();
//    cin >> m;
//    init();
//
//    while (m--)
//    {
//        int k, x;
//        string op;
//        cin >> op;
//        if (op == "L")
//        {
//            cin >> x;
//            pushL(x);
//        }
//        else if (op == "R")
//        {
//            cin >> x;
//            pushR(x);
//        }
//        else if (op == "D")
//        {
//            cin >> k;
//            del(k);
//        }
//        else if (op == "IL")
//        {
//            cin >> k >> x;
//            push(l[k + 1], x);
//        }
//        else
//        {
//            cin >> k >> x;
//            push(k + 1, x);
//        }
//    }
//
//    for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
//    cout << endl;
//
//    return 0;
//}

//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int st[N], tt;
//
//void push(int x)
//{
//    st[++tt] = x;
//}
//
//void pop()
//{
//    tt--;
//}
//
//int query()
//{
//    return st[tt];
//}
//
//bool empty()
//{
//    return tt == 0;
//}
//
//int main()
//{
//    int m;
//    cin >> m;
//
//    while (m--)
//    {
//        int x;
//        string op;
//        cin >> op;
//
//        if (op == "push")
//        {
//            cin >> x;
//            push(x);
//        }
//        else if (op == "pop")
//        {
//            pop();
//        }
//        else if (op == "empty")
//        {
//            if (empty()) cout << "YES" << endl;
//            else cout << "NO" << endl;
//        }
//        else
//        {
//            cout << query() << endl;
//        }
//    }
//
//    return 0;
//}
//
//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int que[N], hh, tt;
//
//void push(int x)
//{
//    que[tt++] = x;
//}
//
//bool empty()
//{
//    return hh == tt;
//}
//
//void pop()
//{
//    hh++;
//}
//
//int query()
//{
//    return que[hh];
//}
//
//int main()
//{
//    int m;
//    cin >> m;
//
//    while (m--)
//    {
//        int x;
//        string op;
//        cin >> op;
//
//        if (op == "push")
//        {
//            cin >> x;
//            push(x);
//        }
//        else if (op == "pop")
//        {
//            pop();
//        }
//        else if (op == "empty")
//        {
//            if (empty()) cout << "YES" << endl;
//            else cout << "NO" << endl;
//        }
//        else
//        {
//            cout << que[hh] << endl;
//        }
//    }
//
//    return 0;
//}
//
//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int st[N], tt;
//
//int main()
//{
//    int n;
//    cin >> n;
//
//    for (int i = 0; i < n; i++)
//    {
//        int x = 0;
//        cin >> x;
//
//        while (tt && st[tt] >= x) tt--;
//        if (tt) cout << st[tt] << ' ';
//        else cout << "-1" << ' ';
//
//        st[++tt] = x;
//    }
//
//    return 0;
//}


